1. Field of the Invention
This invention pertains generally to software prefetching algorithms. More particularly, the invention is a software method and apparatus for inserting prefetch operations according to data flow analysis and, in particular, according to memory operations and associated address forming operations within the program code under consideration.
2. The Prior Art
Current computer systems include, among other things, a memory system and a processing unit (or processor or central processing unit (CPU)). A memory system serves as a repository of information, while the CPU accesses information from the memory system, operates on it, and stores it back.
However, it is well known that CPU clock speeds are increasing at a faster rate than memory speeds. When a processor attempts to read a memory location from the memory system, the request is xe2x80x9cvery urgentxe2x80x9d. That is, in most computer systems, the processor stalls or waits while the memory system provides the data requested to the CPU. The xe2x80x9clatencyxe2x80x9d of the memory is the delay from when the CPU first requests data from memory until that data arrives and is available for use by the CPU.
A cache is a special high-speed memory in addition to the conventional memory (or main memory). FIG. 1 depicts a conventional hierarchical memory system, where a CPU is operatively coupled to a cache, and the cache is operatively coupled to the main memory. By placing the cache (very fast memory) in front of the main memory (large, slow memory), the memory system is able to satisfy most requests from the CPU at the speed of the cache, thereby reducing the overall latency of the system.
When the data requested by the CPU is in the cache (known as a xe2x80x9chitxe2x80x9d), the request is satisfied at the speed of the cache. However, when the data requested by the CPU is not in the cache (known as a xe2x80x9cmissxe2x80x9d), the CPU must wait until the data is provided from the slower main memory to the cache, and then to the CPU, resulting in greater latency.
To address the problem of latency and to increase the xe2x80x9chitxe2x80x9d to xe2x80x9cmissxe2x80x9d ratio associated with cache memory, many modern computer systems have introduced instructions for prefetching data from memory to cache. For example, instructions set architectures (ISA""s), such as SPARC(trademark) V9, support software data prefetch operations. The details of the implementing prefetch operations have been left to the designers of optimizing compilers to find ways to reduce the frequency of cache misses.
One such implementation deals with reducing cache misses associated with loops structures. For example, the following sets forth a portion of code including a loop:
Loop:
Ld [R1], R2
Fadd R2, R3, R4
St R4, [R1]
Add R1, 4, R1
. . .
bcc loop
During compilation of the above code, the loop-based prefetching algorithm will recognize the loop structure and ascertain that the add instruction (Add R1, 4, R1) increments register xe2x80x9cR1xe2x80x9d over and over. The loop-based prefetching algorithm will also recognize that the register xe2x80x9cR1xe2x80x9d is used as an address location for the two memory operations (xe2x80x9cLd [R1], R2xe2x80x9d and xe2x80x9cSt R4, [R1]xe2x80x9d). From the loop structure, the loop-based prefetching algorithm determines that during the next iteration, the load instruction will be for xe2x80x9cLd [R1+4], R2xe2x80x9d. Thus, the loop-based prefetching algorithm may insert an instruction or operation to prefetch the value of a register for a later iteration (e.g., prefetch [R1+4]) during the current iteration, so that when the later iteration is carried out, the value at address R1+4 is in cache.
While useful for loops, the above algorithm is not particularly advantageous for programs without loops or other general purpose programs having complex indirect address references such as pointers, for example. Additionally for highly memory-intensive programs, a solution with analyzes the data flow of the program and inserts the data prefetching operations with respect to an address forming operation and an associated memory operation for the address would be would be particularly beneficial in reducing the frequency of cache misses, thereby increasing the overall speed of the program.
Accordingly, there is a need for a method and apparatus which provides for software prefetching insertion using data flow analysis. The present invention satisfies these needs, as well as others, and generally overcomes the deficiencies found in the background art.
An object of the invention is to provide a method and apparatus for inserting software prefetching operations which overcomes the deficiencies of the prior art.
Another object of the invention is to provide a method and apparatus for inserting software prefetching operations incorporates data flow analysis with respect to memory operations and address forming operations.
Further objects and advantages of the invention will be brought out in the following portions of the specification, wherein the detailed description is for the purpose of fully disclosing the preferred embodiment of the invention without placing limitations thereon.
The present invention is a method and apparatus embodied in software suitable for use with compilation of source code. The invention further relates to machine readable media on which are stored embodiments of the present invention. It is contemplated that any media suitable for retrieving instructions is within the scope of the present invention. By way of example, such media may take the form of magnetic, optical, or semiconductor media.
The present invention also relates to a method and use of prefetch operations to load data from memory into a cache. It is contemplated that the invention may be used for loading data from conventional main memory as well as other xe2x80x9cslowxe2x80x9d data storage structures such as a disk storage or a network storage, for example. Although, the invention is described herein with respect to a single cache, it is contemplated that any suitable cache arrangement (e.g., various levels of cache) is within the scope of the present invention.
In its most general terms, the invention comprises software for inserting prefetch operations based the relative xe2x80x9cdistancexe2x80x9d between an address forming operation and an associated memory operation on the address. The invention is generally used in conjunction and incorporated into compilation software (compiler), which converts source code into a compiled program (or executable file). During compilation, the source code is converted into an intermediary xe2x80x9cprogram codexe2x80x9d which is processed by the compiler. After the compiler has completed processing the program code, a compiled program is generated from the program code.
More particularly, the invention is embodied in a data flow prefetch component having a memory operation locate routine, an address forming operation locate routine, a data flow analysis routine, and a prefetch insert routine.
The memory operation locate routine carries out the operation of finding memory operations (or other prefetchable operation) within the program code under consideration. For example, the memory operation locate routine ascertains or otherwise finds each load or store operation. Each memory operation located by the memory operation locate routine is then processed by the address forming operation locate routine.
The address forming operation locate routine carries out the operation of finding an address forming code sequence associated with a memory operation. In general, for a given memory operation (or other prefetchable operation) located by the memory operation locate routine, the address forming operation locate routine performs a backward dataflow pass from the memory operation. For example, one way to form an address is to place a name of an address location into a register location. Another example of an address forming operation may include indirectly loading address location from a pointer data structure into a register location. Other conventional address forming operations are well known in the art. The address forming operation routine locates such address forming code sequences.
During the backward dataflow pass, the address forming operation routine traverses the program code from the memory operation in the opposite direction of execution flow to find the associated address forming operation.
The address forming operation locate routine further carries out the operation of determining the xe2x80x9cdistancexe2x80x9d between the memory operation as determined by the memory operation locate routine and the associated address forming code sequence as located by the address forming operation locate routine. In an illustrative embodiment, the unit of measure or calculation for determining this distance is the number of CPU cycles (i.e., xe2x80x9cdistancexe2x80x9d) that would be carried out between the two operations. Other units of measure or calculation may also be used with the present invention to ascertain the xe2x80x9cdistancexe2x80x9d between the memory operation and the associated address forming code sequence, such as number of instructions, memory operations, or memory operations that might miss the cache, for example.
The data flow analysis routine carries out the operation of determining whether placing a prefetch operation between the address forming operation and the associated memory operation would be xe2x80x9cprofitablexe2x80x9d. That is, whether a prefetch operation would increase the speed of execution of the program under consideration. In an illustrative embodiment, the prefetch operation is inserted immediately after the address forming operation if deemed profitable.
Several criteria may be used to determine whether inserting a prefetch would be xe2x80x9cprofitablexe2x80x9d including whether the calculated xe2x80x9cdistancexe2x80x9d between the address forming operation and the associated memory operation is sufficient to allow the prefetch operation to complete (i.e., load the cache with the data) before the memory operation is carried out. If so, the prefetch operation would be profitable, because the CPU is able to access the data from the cache rather having to wait for the data to be retrieved from the slower main memory (or other storage device), thereby increasing the speed of the program. Another example, may be where the distance is sufficient to allow the prefetch operation to get started (i.e., begin the process of loading of the cache) before the load operation is carried out. Here, although the cache has not completely been loaded with the requested data, the process of loading the cache has already begun, thereby reducing the CPU""s wait time for the data. As another example, where the memory operation immediately follows the address forming operation, the data flow analysis routine would determine the insertion of the prefetch operation to not be profitable, because in that case, there would not be sufficient time to complete the prefetch operation before the load operation is carried out.
In analyzing whether there is sufficient time to complete the prefetch operation, other factors are taken into account including how such prefetch requests are carried out by the system, for example.
The prefetch insert routine carries out the operation of inserting the prefetch operation if the dataflow analysis routine determines that insertion of the prefetch operation would increase the speed of the program. As noted above, the prefetch operation is inserted immediately after the address forming operation in one embodiment of the invention.
However, in certain cases, where the distance between the address forming operation and the associated memory operation is sufficiently great, it would not be beneficial to place the prefetch operation immediately following the address forming operation. Since the cache is limited in size, older data must be flushed out in order to accommodate newer requests. If the prefetch operation is inserted too far away (e.g., too many CPU cycles) from the memory operation, there is a risk that the data that is prefetched may be flushed from the cache and unavailable to the memory operation. In this case, it would not be profitable to insert the prefetch operation immediately after the address forming operation. Rather, the prefetch operation is inserted at some optimal xe2x80x9cdistancexe2x80x9d before the memory operation such that the prefetch operation is completed at the time (or just slightly before) the memory operation is carried out.
The data flow prefetch component as described above is used in conjunction with a compiler. The compiler normally includes other compilation components for carrying out other compilation tasks as is known in the art. In general, the compiler processes a program code (converted from a source code file) and generates a compiled file (or executable program). The data flow prefetch component executes during this compilation process and carries out the method of the present invention.
In operation, the invention finds a memory operation (or other prefetchable operation) in the program code under compilation. The invention then traverses the program code from the memory operation using a backward dataflow pass to find an associated address forming operation. During the backward dataflow pass, the invention estimates or otherwise calculates the distance (e.g., number of CPU cycles) between the memory operation and the associated address forming operation.
The invention then determines whether insertion of a prefetch operation after the address forming operation would be xe2x80x9cprofitablexe2x80x9d. To this end, the invention determines, among other things, whether the calculated distance is sufficient to allow a prefetch operation placed immediately after the address forming operation to complete (or alternatively, begin its processing) the prefetch sequence before the memory operation takes place. The invention also determines whether the calculated distance is such that the prefetched data may be flushed from the cache before the memory operation takes place. If deemed profitable, the prefetch operation is inserted immediately after the address forming step. Otherwise, the prefetch operation is not inserted.
In an alternative arrangement, if the invention determines that the calculated distance is such that the prefetched data may be flushed from the cache before the memory operation takes place, the prefetch operation is inserted at a calculated distance ahead (i.e., before in execution time) of the memory operation rather than immediately following the address forming operation, where the calculated distance is sufficient xe2x80x9cfarxe2x80x9d (in CPU cycles, for example) from the memory operation to permit the prefetch operation to complete before the memory operation is carried out, but sufficient xe2x80x9cclosexe2x80x9d (in CPU cycles) to the memory operation such that the risk that the prefetched data may be flushed is reduced.
In general, the above acts are carried out for each such memory operation within the program code under compilation.
In an alternative embodiment of the present invention, the data flow prefetch component may include an algorithm to perform instruction scheduling prior to performing the acts described above. For example, the instruction schedule routine may optimally move the memory operation and the address forming operation further apart if the two operations are too close together to permits a prefetch operation to optimize the program. Alternatively, the instruction schedule routine may optimally move the memory operation and the address forming operation closer together if the two operations are too far apart where there is a risk that a data prefetched into the cache would be flushed before the memory operation is carried, as described above.